package ThirdWeek;

import java.util.HashMap;
import java.util.Map;

public class Wednesday {
    //66、加一
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        //我们从后往前进行加1操作，当遇到9的时候不进行加，当不是9的时候进行加1，之后再把加1那个数字之后的值都化为0
        for (int i = n - 1; i >= 0;i--) {
            if (digits[i] != 9) {
                digits[i]++;
                for(int j = i + 1;j < n;j++) {
                    digits[j] = 0;
                }
                return digits;
            }
        }

        //如果数组遍历完到达这里后，说明整个数组都是 9 ，那么把数组扩大一位，0下标为1，其余为0
        int[] ret = new int[n + 1];
        ret[0] = 1;
        return ret;
    }

    //76、最小覆盖子串
    //使用 滑动窗口 + 哈希表
    public String minWindow1(String s, String t) {
        //使用哈希表
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int n = ss.length;
        int m = tt.length;
        Map<Character,Integer> hash1 = new HashMap<>();
        int kinds = 0;
        for (char ch : tt) {
            if (hash1.get(ch) == null || hash1.get(ch) == 0) {
                kinds++;
            }
            hash1.put(ch,hash1.getOrDefault(ch,0) + 1);
        }

        Map<Character,Integer> hash2 = new HashMap<>();
        int minLen = Integer.MAX_VALUE,begin = -1;
        for(int left = 0,right = 0,count = 0;right < n;right++) {
            //进窗口
            char in  = ss[right];
            hash2.put(in,hash2.getOrDefault(in,0) + 1);
            if (hash2.get(in) != null && hash2.get(in).equals(hash1.get(in))) {
                //同一种 种类就count++
                //假如 t是abc
                //s为aabc,那么第一次出现a会增加，第二次就不会了
                count++;
            }
            //判断，当窗口合适的时候进行判断，并且更新结果，并出窗口
            //以前是当，窗口不合适的时候进行判断的
            while(count == kinds) {
                //更新结果，更新字符串长度和从哪里开始
                //当right - left + 1小于最小的长度的时候进行更新
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    begin = left;
                }
                //出窗口
                char out = ss[left++];
                if (hash2.get(out).equals(hash1.get(out))) {
                    //少了一个种类
                    count--;
                }
                hash2.put(out,hash2.get(out) - 1);
            }
        }

        if (begin == -1) {
            return new String("");
        }

        return s.substring(begin,begin + minLen);
    }

    public static String minWindow(String ss, String tt) {
        //使用数组当做哈希表
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int[] hash1 = new int[128]; // 统计字符串 t 中每⼀个字符的频次
        int kinds = 0; // 统计有效字符有多少种
        for (char ch : t)
            if (hash1[ch]++ == 0) kinds++;
        int[] hash2 = new int[128]; // 统计窗⼝内每个字符的频次
        int minlen = Integer.MAX_VALUE, begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
            while (count == kinds) // 判断条件
            {
                if (right - left + 1 < minlen) // 更新结果
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
            }
        }
        if (begin == -1) return new String();
        else return ss.substring(begin, begin + minlen);
    }

    public static void main(String[] args) {
        String s = "aa";
        String t = "aa";
        System.out.println(minWindow(s, t));
    }
}
